public class t1823 {
    public static void main(String[] args) {
        int num = findTheWinner(3,1);
        //System.out.println(num);

    }
    //约瑟夫问题 链表解决
    public static int findTheWinner(int n,int k){
        if(k==1){
            return n;
        }
        per tmp = null;
        per hand = null;//头指针
        //创建环形单链表
        for(int i =1;i<=n;i++){
            if(i==1){
                per per = new per(i);
                tmp = per;
                hand = per;
            }else if(i!=n){
               per per = new per(i) ;
               tmp.next = per;
               tmp = per;
            }else{
                per per = new per(i) ;
                tmp.next = per;
                per.next = hand;
            }
        }
        per root = hand;
        while (true){
            for(int i =0;i<k-1;i++){//保持hand是每个出列的前一个
                hand = root;
                root = root.next;
            }
            hand.next = root.next;//出列的前一个指向出列的后一个
            hand = root.next;//更新开始指针
            root = root.next;//更新开始指针
            if(hand.next == hand){
                break;
            }
        }
        return hand.id;
    }

    public static int yueMath(int n,int m){
        //f(N,M) = (f(N-1),M)+M)%N
        int p = 0;
        for(int i =2;i<=n;i++){
            p = (p+m)%i;
        }
        return p+1;
    }



    public static void show(per hand,int n){
        per tmp = hand;
        while (true){
            if(tmp.next == hand){
                System.out.print(tmp.toString());
                break;
            }else{
                System.out.print(tmp.toString());
                tmp = tmp.next;
            }
        }
        }
    }

class per{
    int id;
    per next;
    public per(int id){
        this.id = id;
    }

    @Override
    public String toString() {
        return id+" ";
    }
}
